package leetcode.interviewClassics;

import leetcode.ListNode;

/**
 * @author Cheng Jun
 * Description: 给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回 null。
 * https://leetcode-cn.com/problems/linked-list-cycle-lcci/
 * @version 1.0
 * @date 2021/11/2 18:53
 */
public class detectCycle {

    public static void main(String[] args) {

    }
    // 使用 set 很好处理，但是不需要 额外空间怎么解决
    // 这个问题其实比较有点难度，但我能讲明白。
    // 设：fast 为快指针，速度为2，slow为慢指针，速度为1
    // （如果存在环，则两个指针最后都会进入环，而且快指针一定会和慢指针相遇（并且慢指针没有走完一整圈，如果走完一整圈，那么快指针走完了两圈多，会相遇的））.
    // 假设：相遇时fast 在环中走了 n 圈，环的长度为 c，a 为起点到环点距离，b 为环点到相遇点距离，环点到相遇点的距离为 c - b
    // 证明：当相遇时，fast 走过的路程为 a + n*c + b ，slow 走过的路程为 a+b，
    // 又因为fast 的速度是 slow 的两倍，相同时间内，任意时刻，fast 走过的路程 为 slow 走过的路程两倍。
    // 所以 a + n*c + b = 2(a+b) 推导出 a = (c-b) + (n-1)*c
    // 也就是 a 的距离等于 环点到相遇点的距离 + 整数倍的环长度，那么慢指针在相遇后，再走上 整数倍的环长度（走整数倍就是相当于原地踏步）和 c-b 的距离就到了环点。
    // 在相遇后，再定义一个指针 slow1，速度为1。相遇后slow 和 slow1 同时走，slow1 走了 a 距离 到达环点。
    // 那么slow 也走了 a 距离，其实就是 走了 整数倍的环长度和 c-b，slow 也会到达环点。

    static ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode first = head;
        ListNode slow = head;
        while (first != null) {
            // 慢指针走一步，快指针走两步，快指针肯定先到尾节点（没有环的话）
            slow = slow.next;
            if (first.next != null) {
                first = first.next.next;
            } else {
                // first.next 为null 表示到达尾节点，没有环
                return null;
            }
            // 前进一次，比较一次 first 和 slow 是否相等
            if (first == slow) {
                // 弄一个slow1 从头走，然后和 slow 比较
                ListNode slow1 = head;
                while (slow1 != slow) {
                    // 两个指针，每次走一步，迟早会在环点相遇
                    slow = slow.next;
                    slow1 = slow1.next;
                }
                return slow;
            }
        }
        return null;

    }
}
